Кластерный анализ
Кластерный анализ ( ) — задача разбиения заданной выборки объектов (ситуаций) на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя. Типология задач кластеризации Типы входных данных * Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками. Признаки могут быть числовыми или нечисловыми. * Матрица расстояний между объектами. Каждый объект описывается расстояниями до всех остальных объектов обучающей выборки. Цели кластеризации * Понимание данных путём выявления кластерной структуры. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»). * Сжатие данных. Если исходная выборка избыточно большая, то можно сократить её, оставив по одному наиболее типичному представителю от каждого кластера. * Обнаружение новизны ( ). Выделяются нетипичные объекты, которые не удаётся присоединить ни к одному из кластеров. В первом случае число кластеров стараются сделать поменьше. Во втором случае важнее обеспечить высокую степень сходства объектов внутри каждого кластера, а кластеров может быть сколько угодно. В третьем случае наибольший интерес представляют отдельные объекты, не вписывающиеся ни в один из кластеров. Во всех этих случаях может применяться иерархическая кластеризация, когда крупные кластеры дробятся на более мелкие, те в свою очередь дробятся ещё мельче, и т. д. Такие задачи называются задачами таксономии. Результатом таксономии является древообразная иерархическая структура. При этом каждый объект характеризуется перечислением всех кластеров, которым он принадлежит, обычно от крупного к мелкому. Классическим примером таксономии на основе сходства является биноминальная номенклатура живых существ, предложенная Карлом Линнеем в середине XVIII века. Аналогичные систематизации строятся во многих областях знания, чтобы упорядочить информацию о большом количестве объектов. Методы кластеризации * K-средних (то есть K-means) * Графовые алгоритмы кластеризации * Статистические алгоритмы кластеризации * Алгоритм ФОРЕЛЬ * Иерархическая кластеризация или таксономия * Нейронная сеть Кохонена * Ансамбль кластеризаторов Формальная постановка задачи кластеризации Пусть X~ — множество объектов, Y~ — множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами \rho(x,x')~ . Имеется конечная обучающая выборка объектов X^m = \{ x_1, \dots, x_m \} \subset X . Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике \rho~ , а объекты разных кластеров существенно отличались. При этом каждому объекту x_i\in X^m приписывается номер кластера y_i~ . Алгоритм кластеризации — это функция a\colon X\to Y , которая любому объекту x\in X ставит в соответствие номер кластера y\in Y . Множество Y~ в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации. Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем, что метки исходных объектов y_i~ изначально не заданы, и даже может быть неизвестно само множество Y~ . Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин: * не существует однозначно наилучшего критерия качества кластеризации. Известен целый ряд эвристических критериев, а также ряд алгоритмов, не имеющих чётко выраженного критерия, но осуществляющих достаточно разумную кластеризацию «по построению». Все они могут давать разные результаты. * число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым субъективным критерием. * результат кластеризации существенно зависит от метрики, выбор которой, как правило, также субъективен и определяется экспертом. Применение В биологии В социологии В информатике * Группирование результатов поиска: Кластеризация используется для "интеллектуального" группирования результатов при поиске файлов, веб-сайтов, других объектов, предоставляя пользователю возможность быстрой навигации, выбора заведомо более релевантного подмножества и исключения заведомо менее релевантного — что может повысить юзабилити интерфейса по сравнению с выводом в виде простого сортированного по релевантности списка. ** Clustyhttp://clusty.com/ - кластеризующая поисковая машина компании Vivísimo ** Nigma - российская поисковая система с автоматической кластеризацией результатов ** Quintura - визуальная кластеризация в виде облака ключевых слов * Сегментация изображений (image segmentation): Кластеризация может быть использована для разбиения цифрового изображения на отдельные области с целью обнаружения границ (edge detection) или распознавания объектов. * Интеллектуальный анализ данных (data mining) См. также * Кластеризация документов * Классификация документов * Нейронные сети Литература # Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989. # Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8. # Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9. # Мандель И. Д. Кластерный анализ. — М.: Финансы и статистика, 1988. ISBN 5-279-00050-7. # Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. ISBN 966-00-0341-2. # Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5. # Jain, Murty, Flynn '' Data clustering: a review. // ACM Comput. Surv. '''31'(3) , 1999 Внешние ссылки На русском языке * www.MachineLearning.ru — профессиональный вики-ресурс, посвященный машинному обучению и интеллектуальному анализу данных * BaseGroup.ru: Кластеризация * С. Николенко. Слайды лекций по алгоритмам кластеризации На английском языке *''COMPACT - Comparative Package for Clustering Assessment. A free Matlab package, 2006. * P. Berkhin, ''Survey of Clustering Data Mining Techniques, Accrue Software, 2002. * Jain, Murty and Flynn: Data Clustering: A Review, ACM Comp. Surv., 1999. * for another presentation of hierarchical, k-means and fuzzy c-means see this introduction to clustering. Also has an explanation on mixture of Gaussians. * David Dowe, Mixture Modelling page - other clustering and mixture model links. * a tutorial on clustering http://gauss.nmsu.edu/~lludeman/video/ch6pr.html * The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay includes chapters on k-means clustering, soft k-means clustering, and derivations including the E-M algorithm and the variational view of the E-M algorithm. * An overview of non-parametric clustering and computer vision * "The Self-Organized Gene", tutorial explaining clustering through competitive learning and self-organizing maps. * kernlab - R package for kernel based machine learning (includes spectral clustering implementation) * Tutorial - Tutorial with introduction of Clustering Algorithms (k-means, fuzzy-c-means, hierarchical, mixture of gaussians) + some interactive demos (java applets) * Data Mining Software - Data mining software frequently utilizes clustering techniques. * Java Competitve Learning Application A suite of Unsupervised Neural Networks for clustering. Written in Java. Complete with all source code. * Machine Learning Software - Also contains much clustering software. *[http://cism.kingston.ac.uk/people/shihab/dissertation.pdf Fuzzy Clustering Algorithms and their Application to Medical Image Analysis PhD Thesis, 2001, by AI Shihab.] * Cluster Computing and MapReduce Lecture 4 Категория:Применение искусственного интеллекта Категория:Математическая статистика Категория:Анализ данных ca:Clusterització de dades cs:Shluková analýza de:Clusteranalyse en:Cluster analysis es:Algoritmo de agrupamiento fr:Partitionnement de données hr:Grupiranje it:Clustering ja:データ・クラスタリング pl:Analiza skupień pt:Clustering sl:Grupiranje th:การแบ่งกลุ่มข้อมูล vi:Phân nhóm dữ liệu zh:数据聚类